﻿using Enyim.Collections;
using Npgsql;
using NpgsqlTypes;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BTL
{
    internal class Data : IComparable<Data>
    {
        public string Value { get; set; }

        public double Distance { get; set; }

        public Data()
        {
        }

        public Data(string value, double distance)
        {
            Value = value;
            Distance = distance;
        }

        public int CompareTo(Data other)
        {
            if (other != null)
                return Distance.CompareTo(other.Distance);
            return 1;
        }
    }

    internal class Program
    {
        private delegate double DistanceDelegate(NpgsqlPoint p, Envelope envelope);

        private static RTree<string> tree;
        private static List<Data> result = new List<Data>();

        private static void Main(string[] args)
        {
            string c = "k";
            do
            {
                double x, y, scale = 1;
                int algorithm, distance, k;
                string place;
                if (tree == null)
                {
                    Console.Write("Nhap loai dia diem (city, village, town): ");
                    place = Console.ReadLine();
                    ReadData(place);
                }
                else
                {
                    Console.Write("Co nhap lai du lieu khong? (c/k): ");
                    var ch = Console.ReadLine();
                    if (ch == "c")
                    {
                        Console.Write("Nhap loai dia diem (city, village, town): ");
                        place = Console.ReadLine();
                        ReadData(place);
                    }
                }
                Console.WriteLine("Nhap toa do:");
                Console.Write("X = ");
                x = double.Parse(Console.ReadLine());
                Console.Write("Y = ");
                y = double.Parse(Console.ReadLine());
                Console.Write("So luong can tim k = ");
                k = int.Parse(Console.ReadLine());
                Console.WriteLine("Chon ham khoang cach:");
                Console.WriteLine("1. Min dist");
                Console.WriteLine("2. Min max dist");
                distance = int.Parse(Console.ReadLine());
                DistanceDelegate f = null;
                switch (distance)
                {
                    case 1:
                        f = MinDist;
                        break;

                    case 2:
                        f = MinMaxDist;
                        break;
                }
                Console.WriteLine("Chon thuat toan:");
                Console.WriteLine("1. Tim kiem tham lam");
                Console.WriteLine("2. Tim kiem su dung hang doi");
                Console.WriteLine("3. Tim kiem tham lam mo rong");
                algorithm = int.Parse(Console.ReadLine());
                switch (algorithm)
                {
                    case 3:
                        Console.Write("Ti le mo rong scale = ");
                        scale = double.Parse(Console.ReadLine());
                        break;
                }
                result.Clear();
                Stopwatch watch = new Stopwatch();
                watch.Start();
                switch (algorithm)
                {
                    case 1:
                        SearchWithGreedy(new NpgsqlPoint(x, y), k, f);
                        break;

                    case 2:
                        SearchWithPriorityQueue(new NpgsqlPoint(x, y), k, f);
                        break;

                    case 3:
                        SearchWithGreedyOpen(new NpgsqlPoint(x, y), k, f, scale);
                        break;
                }
                watch.Stop();
                Console.WriteLine("Thoi gian thuc hien: {0} ms", watch.Elapsed.TotalMilliseconds);
                Console.WriteLine("Ket qua:");
                foreach (var item in result)
                {
                    Console.WriteLine("{0,-30}{1}", item.Value, item.Distance);
                }
                Console.Write("Co thuc hien tiep khong? (c/k): ");
                c = Console.ReadLine();
            }
            while (c == "c");
        }

        private static void ReadData(string place)
        {
            Console.WriteLine("Read database and create index...");
            tree = new RTree<string>(4);
            NpgsqlConnection conn = new NpgsqlConnection("Username=postgres; Password=123456; Database=postgres; Host=localhost;");
            conn.Open();
            NpgsqlCommand command = new NpgsqlCommand(string.Format("SELECT name,geom::POINT FROM placeasiapoints WHERE place='{0}'", place), conn);
            NpgsqlDataReader dr = command.ExecuteReader();
            int count = 0;
            while (dr.Read())
            {
                count++;
                string name = dr[0].ToString();
                NpgsqlPoint a = (NpgsqlPoint)dr[1];
                tree.Insert(new RTreeNode<string>(name, new Envelope(a.X, a.Y, a.X, a.Y)));
            }
            conn.Close();
            Console.WriteLine("Read database completed. There are {0} records", count);
        }

        private static void SearchWithPriorityQueue(NpgsqlPoint p, int k, DistanceDelegate distance)
        {
            int num = k;
            var node = tree.Root;
            PriorityQueue<KeyValuePair<RTreeNode<string>, double>> U = new PriorityQueue<KeyValuePair<RTreeNode<string>, double>>(Comparer<KeyValuePair<RTreeNode<string>, double>>.Create((a, b) => { return a.Value.CompareTo(b.Value); }));
            U.Push(new KeyValuePair<RTreeNode<string>, double>(node, distance(p, node.Envelope)));

            while (U.Count > 0)
            {
                var e = U.Pop();
                if (e.Key.Data == null)
                {
                    foreach (var item in e.Key.Children)
                    {
                        U.Push(new KeyValuePair<RTreeNode<string>, double>(item, distance(p, item.Envelope)));
                    }
                }
                else
                {
                    num--;
                    result.Add(new Data(e.Key.Data, e.Value));
                    if (num == 0)
                        return;
                }
            }
        }

        private static void SearchWithGreedy(NpgsqlPoint p, int k, DistanceDelegate distance)
        {
            Search2(p, k, distance, tree.Root);
        }

        private static void SearchWithGreedyOpen(NpgsqlPoint p, int k, DistanceDelegate distance, double scale)
        {
            Search2(p, (int)(k * scale), distance, tree.Root);
            result.Sort();
            result = result.Take(k).ToList();
        }

        private static void Search2(NpgsqlPoint p, int k, DistanceDelegate distance, RTreeNode<string> node)
        {
            List<KeyValuePair<RTreeNode<string>, double>> nodes = new List<KeyValuePair<RTreeNode<string>, double>>();
            foreach (var item in node.Children)
            {
                nodes.Add(new KeyValuePair<RTreeNode<string>, double>(item, distance(p, item.Envelope)));
            }
            nodes.Sort(Comparer<KeyValuePair<RTreeNode<string>, double>>.Create((x, y) => { return x.Value.CompareTo(y.Value); }));
            foreach (var item in nodes)
            {
                if (result.Count >= k)
                    return;
                if (item.Key.Data != null)
                {
                    result.Add(new Data(item.Key.Data, item.Value));
                }
                else Search2(p, k, distance, item.Key);
            }
        }

        private static double Distance(NpgsqlPoint p1, NpgsqlPoint p2)
        {
            return (p1.X - p2.X) * (p1.X - p2.X) + (p1.Y - p2.Y) * (p1.Y - p2.Y);
        }

        private static double Module(double dx, double dy)
        {
            return Math.Sqrt(dx * dx + dy * dy);
        }

        private static double MinDist(NpgsqlPoint p, Envelope envelope)
        {
            if (envelope.X1 <= p.X && envelope.X2 >= p.X && envelope.Y1 <= p.Y && envelope.Y2 >= p.Y)
                return 0;
            double r1, r2;
            if (p.X < envelope.X1)
                r1 = envelope.X1;
            else if (p.X > envelope.X2)
                r1 = envelope.X2;
            else r1 = p.X;
            if (p.Y < envelope.Y1)
                r2 = envelope.Y1;
            else if (p.Y > envelope.Y2)
                r2 = envelope.Y2;
            else r2 = p.Y;
            return Module(p.X - r1, p.Y - r2);
        }

        private static double MinMaxDist(NpgsqlPoint p, Envelope envelope)
        {
            if (envelope.X1 <= p.X && envelope.X2 >= p.X && envelope.Y1 <= p.Y && envelope.Y2 >= p.Y)
                return 0;
            var rm1 = p.X <= (envelope.X1 + envelope.X2) / 2 ? envelope.X1 : envelope.X2;
            var rM1 = p.X >= (envelope.X1 + envelope.X2) / 2 ? envelope.X1 : envelope.X2;
            var rm2 = p.Y <= (envelope.Y1 + envelope.Y2) / 2 ? envelope.Y1 : envelope.Y2;
            var rM2 = p.Y <= (envelope.Y1 + envelope.Y2) / 2 ? envelope.Y1 : envelope.Y2;
            return Math.Min(Module(p.X - rm1, p.Y - rM2), Module(p.Y - rm2, p.X - rM1));
        }
    }
}